#include <stdio.h>
#include <time.h>
#include <stdlib.h>

//

typedef int ElemType;
typedef struct
{
    ElemType * data;
    int length;        //数组长度
}SSTable;

void st_init(SSTable &ST, int len)
{
    ST.length=len;
    ST.data=(ElemType*)malloc(sizeof(ElemType)*(len));  //开辟数组空间
    //填入随机数
    srand(time(NULL));
    for(int i=0; i<ST.length; i++)
    {
        ST.data[i]=rand()%100;   //0~99的随机数
    }
}

//打印数组
void st_print(SSTable &ST)
{
    for(int i=0; i<ST.length; i++)
    {
        printf("%3d",*(ST.data+i));
    }
    printf("\n");
}

//排序
int compare(const void* e1,const void* e2)
{
    return *(ElemType*)e1 - *(ElemType*)e2;
}

//二分查找（折半查找）
int binary_search(SSTable &st,ElemType key)
{
    int low=0;
    int high=st.length-1;
    int mid=(low+high)/2;
    while(low<=high)
    {
        if(key > st.data[mid])
        {
            low=mid+1;
            mid=(low+high)/2;
        }
        else if(key < st.data[mid])
        {
            high=mid-1;
            mid=(low+high)/2;
        }
        else
        {
            return mid;
        }

    }
    return -1;
}

int main() {
    SSTable st;            //创建数组
    st_init(st,10); //初始化，随机生成十个数
    st_print(st);       //打印数组
    qsort(st.data,st.length,sizeof(ElemType),compare);     //排序数组
    st_print(st);       //打印排序后的数组
    printf("please input key:");
    ElemType key;
    scanf("%d",&key);
    int ret=binary_search(st,key);
    if(ret!=-1)
    {
        printf("the key index is %d\n",ret);
    }
    else
    {
        printf("not find it\n");
    }
    return 0;
}
